Set Theory

1. Failure of Intuition
2. Axiomatic Set Theory
- 2.1. ZFC
3. Pair
4. Cartesian Product
5. Relation
6. Function
7. Properties
- 7.1. Well-Founded
8. Set Operations
- 8.1. Cartesian Product
  - 8.1.1. Properties
- 8.2. Symmetric Difference
  - 8.2.1. Definition
  - 8.2.2. Properties
9. Empty Set
10. De Morgan's Laws
- 10.1. Statement
11. Net
- 11.1. Definition
12. Filter
- 12.1. Definition
13. Family
14. Class
- 14.1. Definition
- 14.2. Proper Class
15. Infinities
- 15.1. Aleph Number
- 15.2. Beth Number
16. References

1. Failure of Intuition

Set can be formed from the class of all objects satisfying any defining condition.

1.1. Russell's Paradox

Let \(y = \{x : x\not\in x\}\). Is \(y\) in \(y\)?

1.2. Cantor's Paradox

There is no set of all cardinalities.

1.3. Burali-Forti Paradox

Set of all ordinal numbers.

2. Axiomatic Set Theory

2.1. ZFC

Zermelo-Fraenkel Set Theory with Axiom of Choice

2.1.1. Axiom of Extensionality

Two sets are equal if they have the same elements.

2.1.2. Axiom of Regularity

Axiom of Foundation
Every non-empty set \(x\) contains a member \(y\) such that \(x\) and \(y\) are disjoint sets.

2.1.3. Axiom Schema of Specification

Axiom Schema of Separation, Axiom Schema of Restricted Comprehension
Subset obeying a formula always exists.
- Note that the paradoxical set in Russell's paradox is not a subset of another set.

2.1.4. Axiom of Pairing

If \(x\) and \(y\) are sets, then there exists a set which contains \(x\) and \(y\) as elements.

2.1.5. Axiom of Union

The union over the elements of a set exists.

2.1.6. Axiom Schema of Replacement

The image of a set under any definable function will also fall inside a set.

2.1.7. Axiom of Infinity

Informally, there exists a set having infinitely many members.

2.1.8. Axiom of Power Set

For any set \(x\), there is a set \(y\) that contains every subset of \(x\).

2.1.9. Axiom of Well-Ordering

For any set \(x\), there exists a binary relationship \(R\) which well-orders \(x\).
The Axiom of Choice - YouTube

2.1.9.1. Statement

\(\exists f\colon X \to \bigcup X\) such that \(f(x) \in x\).

2.1.9.2. Corollary

For a surjective function \(f\colon X \to Y\), there exists an injective function \(g\colon Y\to X\), such that \(g(y) = \mathrm{choice}(X_y)\).

2.1.9.3. Zorn's Lemma

2.1.9.3.1. Statement

For a partially ordered set \(X\), if there exists upper bound for every chain \(C\subseteq X\), then \(X\) has a maximal element.

2.1.9.4. Well-Ordering Theorem

Every set can be well-ordered.
Well-ordering theorem - Wikipedia

3. Pair

\[ (a, b) := \{\{a\}, \{a, b\}\}. \]

4. Cartesian Product

\[ X\times Y := \{(x, y) \mid x\in X, y\in Y\}. \]

5. Relation

\[ R := R \subseteq X\times Y \] \[ xRy \iff (x, y)\in R \]

6. Function

\(f\) is defined by the relation \(R := \{ (x, f(x)) \mid \forall x \in X \}\).
\[ f := (R, X, Y) \]

6.1. Definition

A function with domain \(X\) and codomain \(Y\) is a binary relation \(R\) between \(X\) and \(Y\) that satisfies:
- \(\forall x\in X, \exists y\in Y: (x,y)\in R\)
- \((x,y)\in R\land (x,z)\in R\implies y = z\)

6.2. Additive Function

6.2.1. Defintion

A function \(f\) that satisfies: \[ f(x+y) = f(x) + f(y). \]

6.2.2. Cauchy's Functional Equation

The equation above over the real number.
This can have pathological solutions, unless restricted by any of the following regularity conditions:
- \(f\) is continuous at one point.
- \(f\) is monotonic on any interval.
- \(f\) is bounded on any interval.
- \(f\) is Lebesgue measurable.

Note that \(f(x) = cx\) are the solution.

6.3. Multiplicative Function

A function \(f\) that satisfies: \[ f(ab) = f(a)f(b) \] if \(a\) and \(b\) are coprime.
- Note that \(f(x) = x^n\) are also the solutions.

6.3.1. Completely Multiplicative Function

\[ f(ab) = f(a)f(b) \] for all positive integers.

6.3.2. Examples

Euler's totient function
Möbius function
Liouville Function
Dirichlet Characters
Legendre symbol
Jacobi Symbol

7. Properties

7.1. Well-Founded

\[ \forall S\subseteq X, \exists x_0\in X\colon \forall s \in S, x_0 \le s. \]

8. Set Operations

8.1. Cartesian Product

\( A\times B \)

8.1.1. Properties

Cartesian product distributes over most of the set operations:

\[ A\times (B\setminus C) = (A\times B)\setminus (A\times C) \]
\[ A\times (B\cup C) = (A\times B)\cup (A\times C) \]
\[ A\times (B\cap C) = (A\times B)\cap (A\times C) \]
\[ A\times (B\triangle C) = (A\times B)\triangle (A\times C) \]

8.2. Symmetric Difference

Disjunctive Union, Set Sum
\(A\vartriangle B\) (traditionally \(A\mathbin{\Delta}B\))
\(A\oplus B\), \(A\ominus B\) when viewed as the addition modulo 2.

8.2.1. Definition

\(A \vartriangle B = (A\setminus B)\cup (B\setminus A)\)

8.2.2. Properties

Associative
Commutitive

9. Empty Set

\[ \forall x\in\varnothing,\ 2 \mid x \implies 2 \nmid x \] evaluates to true.

10. De Morgan's Laws

De Morgan's Theorem

10.1. Statement

10.1.1. Mathematical logics

\[ \neg (A \land B) = \neg A \lor \neg B \]
\[ \neg (A \lor B) = \neg A \land \neg B \]

10.1.2. Set theory

\[ (A \cup B)^{C} = A^{C} \cap B^{C} \]
\[ (A \cap B)^{C} = A^{C} \cup B^{C} \]
It can be generalized into any number of sets, including countable and uncountable infinity:
- \[ \overline{\bigcup_{i\in I}A_i} = \bigcap_{i\in I} \overline{A_i} \]
- \[ \overline{\bigcap_{i\in I}A_i} = \bigcup_{i\in I} \overline{A_i} \]

10.1.3. Computer Science

excalidraw:./de_morgan.excalidraw.svg

11. Net

Moore-Smith Sequence

11.1. Definition

A Function \(x_\bullet\colon A\to X\) from a directed set \(A\), to a space \(X\).
Denoted \[ x_\bullet = (x_a)_{a\in A}. \]

12. Filter

Intuitively, collection of large subsets that serves special purposes.

12.1. Definition

A filter on a set \(X\) is a family \(\mathcal{B}\) of subsets such that:
- Proper: \(X\in \mathcal{B}\) and \(\varnothing \not\in \mathcal{B}\)
- Closure under Finite Intersections: \(A\in \mathcal{B}\land B\in \mathcal{B} \implies A\cap B\in \mathcal{B}\)
- Isotony: \(A \subset B\subset X\land A\in \mathcal{B} \implies B\in \mathcal{B}\)

13. Family

Or Collection

Family can mean any of:

Set
Indexed Set
Multiset
Class

14. Class

14.1. Definition

Collection of objects that can be unambiguously defined by a property that all its members share.

14.2. Proper Class

A class that is not a set.

15. Infinities

15.1. Aleph Number

Cardinality of inifnite sets that can be well-ordered.

The \( \aleph_0 \) is the cardinality of the natural number. And the next \( \aleph \) are built on top of that.

15.2. Beth Number

The \( \beth_0 \) is \( \aleph_0 \). \[ \beth_{\alpha+1} = 2^{\beth_\alpha}. \]

Unless the generalized continuum hypothesis is true, there are numbers indexed by \( \aleph \) that are not indexed by \( \beth \).